package stack;

import java.util.Deque;
import java.util.LinkedList;

/*
* 42. 接雨水
*    单调栈解法
* */
public class Trap42 {
    public int trap(int[] height){
        Deque<Integer> stack = new LinkedList<>();
        int res=0;
        for(int i=0;i<height.length;i++){
            while(!stack.isEmpty() && height[i]>=height[stack.peek()]){
                int top = stack.pop();
                if(stack.isEmpty()){
                    break;
                }
                int left=stack.peek();
                int currWidth=i-left-1;
                int currHeight=Math.min(height[left],height[i])-height[top];
                res+=currHeight*currWidth;
            }
            stack.push(i);
        }
        return res;
    }
}
